package com.wc.fortnight_blue_bridge.Q16模拟二.D_最少代价;

import java.util.Arrays;

/**
 * @Author congge
 * @Date 2024/11/23 21:36
 * @description
 * https://dasai.lanqiao.cn/pages/v7/dasai/prelim/prelim_examing.html?examUsperPaperId=338843&applyId=579285787961
 */
public class Main {
    /**
     * 【问题描述】
     * 小蓝有一个整数，初始值为 1 ，他可以花费一些代价对这个整数进行变换。
     * 小蓝可以花费 1 的代价将整数增加 1 。
     * 小蓝可以花费 3 的代价将整数增加一个值，这个值是整数的数位中最大的那个（1 到 9）。
     * 小蓝可以花费 10 的代价将整数变为原来的 2 倍。
     * 例如，如果整数为 16，花费 3 将整数变为 22 。
     * 又如，如果整数为 22，花费 1 将整数变为 23 。
     * 又如，如果整数为 23，花费 10 将整数变为 46 。
     * 请问，如果要将整数从初始值 1 变为 2024，请问最少需要多少代价？
     */
    static int N = 5010, M = N << 2, INF = 0x3f3f3f3f;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int[] dist = new int[N], q = new int[N];
    static boolean[] st = new boolean[N];
    static int[] pre = new int[N];
    static int n = 2024, idx = 1;

    public static void main(String[] args) {
        for (int i = 1; i <= 2024; i++) {
            add(i, i + 1, 1);
            add(i, i + digmax(i), 3);
            add(i, i * 2, 10);
        }
        spfa();
        int x = 2024;
        while (pre[x] > 0){
            System.out.print(x + " ");
            x = pre[x];
        }
        System.out.println();

        System.out.println(dist[n]);
    }

    static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void spfa(){
        Arrays.fill(dist, INF);
        dist[1] = 0;
        int hh = 0, tt = 1;
        q[0] = 1;
        st[1] = true;
        while (hh != tt){
            int t = q[hh++];
            if (hh == N) hh = 0;
            st[t] = false;
            for (int i = h[t]; i > 0; i = ne[i]){
                int j = e[i];
                if (dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    pre[j] = t;
                    if (!st[j]){
                        q[tt++] = j;
                        if (tt == N) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
    }

    static int digmax(int x){
        int res = 0;
        while (x > 0){
            res = Math.max(res, x % 10);
            x /= 10;
        }
        return res;
    }
}
